#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if (root == nullptr)
        {
            return ans;
        }
        q.push(root);
        while (!q.empty())
        {
            vector<int> path;
            int n = q.size();
            for (int i = 0; i < n; i++)
            {
                TreeNode* tmp = q.front();
                q.pop();
                path.push_back(tmp->val);
                if (tmp->left != nullptr)
                {
                    q.push(tmp->left);
                }
                if (tmp->right != nullptr)
                {
                    q.push(tmp->right);
                }
            }
            ans.push_back(path);
        }
        return ans;
    }
};

int main()
{
    TreeNode* node1 = new TreeNode(3);
    TreeNode* node2 = new TreeNode(9);
    TreeNode* node3 = new TreeNode(20);
    TreeNode* node4 = new TreeNode(15);
    TreeNode* node5 = new TreeNode(7);

    node1->left = node2;
    node1->right = node3;
    node3->left = node4;
    node3->right = node5;

    Solution s;
    vector<vector<int> > ans = s.levelOrder(node1);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << "[";
        for (int j = 0; j < ans[i].size() - 1; j++)
        {
            cout << ans[i][j] << ",";
        }
        cout << ans[i][ans[i].size() - 1];
        cout << "]" << endl;
    }
    return 0;
}